package com.fr.lintcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Q1434 {
    /**
     * @param N:
     *            an integer
     * @param edges:
     *            the edges
     * @return: a list ans, where ans[i] is the sum of the distances between node i and all other nodes
     */
    // 超时
    public int[] sumOfDistancesInTree(int N, int[][] edges) {
        // Write your code here
        if (N == 0 || edges == null || edges.length == 0) {
            return new int[N];
        }
        int[] rs = new int[N];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            List<Integer> l0 = map.get(edge[0]);
            if (l0 == null) {
                l0 = new ArrayList<>();
                map.put(edge[0], l0);
            }
            l0.add(edge[1]);
            List<Integer> l1 = map.get(edge[1]);
            if (l1 == null) {
                l1 = new ArrayList<>();
                map.put(edge[1], l1);
            }
            l1.add(edge[0]);

        }
        for (int i = 0; i < N; i++) {
            rs[i] = cal(i, map);
        }
        return rs;
    }

    private int cal(int i, Map<Integer, List<Integer>> map) {
        List<Integer> list = map.get(i);
        int sum = 0;
        int d = 1;
        Set<Integer> set = new HashSet<>();
        set.add(i);
        while (list != null && list.size() > 0) {
            List<Integer> tmp = new ArrayList<>();
            for (int num : list) {
                set.add(num);
                List<Integer> numList = map.get(num);
                if (numList != null) {
                    tmp.addAll(numList);
                }
                sum += d;
            }
            tmp.removeAll(set);
            list = tmp;
            d++;
        }
        return sum;
    }

}
